ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group01b.txt/000065_icon-group-sender_Thu Apr 26 08:27:30 2001.msg

Internet Message Format | 2002-01-03 | 6KB

Return-Path: <icon-group-sender>
Received: (from root@localhost)
    by baskerville.CS.Arizona.EDU (8.11.1/8.11.1) id f3QFOqU08842
    for icon-group-addresses; Thu, 26 Apr 2001 08:24:52 -0700 (MST)
Message-Id: <[e-mail]>
Date: Wed, 25 Apr 2001 18:55:31 -0500
From: [e-mail]
Subject: [ICON]Answer.... for someone else ;)
To: [e-mail]
Cc: [e-mail]
Errors-To: [e-mail]
Status: RO
Content-Length: 5152

Passing along by request this interesting reply to the "rotating numbers"
thread....

<---- Begin Forwarded Message ---->
From: [e-mail]
To: [e-mail]
Subject: [ICON]Answer.... for someone else ;)
Date: Wed, 25 Apr 2001 21:21:24 +0200

Hi,
Greetings from Koeln/Germany. ;)

It's for someone from icon-group@...
AFAIK you're subscribed, too.
Because I cannot [it's only beginning of my CANNOTS list ;(((  ] subscribe
(read:answer) using this address -- pls. fwd :)

Few weeks ago on the icon-group someone wrote:
> > >> 142857 is a cyclic number, the numbers of which always appear in the
> > >> same order but rotated around when multipled by any number from 1 to
6.
> > >>
> > >> 142857 * 2 = 285714
> > >> 142857 * 3 = 428571
> > >> 142857 * 4 = 571428
> > >> 142857 * 5 = 714285
> > >> 142857 * 6 = 857142
> > >>
> > >> So can you find any more numbers like this? Is there a simple
algorithm
> > >> for finding them or is this another good application for parallel
> > >> machines?
> >

I forwarded this message to _other_ group (over 100 msg in thread!!!!!).
One of the most relevant answers is:

> > The reason this number has such magical properties is because it is the
> > number (1/7) * 100_000.  The fraction 1/7 has a repeating series of
digits
> > "142857".  And, when you multiply this fraction by 2, 3, 4, ..., the
> > digits appear in a shuffled order; thus, 142857 is just an employment of
> > 1/7's magic.
>
> But this does not explain _why_ it happens.
> E.g. why does it work with 1/7 and not with 1/3, 1/11, 1/13... ?
>
> To make the question more general:
> Find all integers a, n with 1 < a < n such that the digits of the
> fraction a/n are a rotation of the digits of the fraction 1/n.
>
> Examples:
> (a,n) = (2,7), (3,7), ... , (6,7); (10,11); (3,13), (4,13), (9,13), ...
>
> I don't know how difficult is this question.
> When you've solved it in base 10 you can try it in arbitrary base D.

Sure!

First I had to narrow down the problem a bit to make it manageable. Now that
I
know more, I suppose I could give it a wider shot, but I'm tired and
underequipped, anyways.

Task: find number-pairs D,n where for n applies:

for every m in [1,n[, the period in numeric representation of m/n in base D
is
the period of 1/n with sufficient rotating shift.

For example:

1/7 = 0.142857...
2/7 = 0.  285714...
3/7 = 0. 428571...

And so on. So, obviously, one such (D,n) is (10,7). And now on the findings:

Any 1/n whose numeric representation's period is n-1 digits in length is
rotating. I also know that if there's no trailing sequence, that is, the
period
starts right after decimal (D'mal) point, then the complete rotation (all
m/n)
is only possible if the period is n-1 digits.

And you can find rotating (D,n):s like this:

For some (D,n), find smallest p for which it is true that:

(D^p-1) % n = 0

[% is integer modulo, like in C]

In other words, that (D^p-1) is divisible with n. Now, if
p=n-1
then (D,n) is the rotating pair that we were looking for.

That much I could prove so far. On the hunches department: All n, regardless
of
D, that I could find, are primes.

If it's true that (D^(n-1)-1) % n = 0 but n-1 is not the smallest power that
executes that, then it's not completely rotating but it seems it /might/ be
still rotating for some parts.

Other way to find these numbers, likely more CPU-intensive (isn't there a
builtin modulo instruction in x86 cpus or something?) but can handle much
larger numbers:

f(0)=1
f(x)=(D*f(x-1)) % n

If the first value of f after x=0 is at n-1, then (D,n) is rotating.

--

If my ranting is too confusing, I've attached a code to find for such pairs.
Thank you for your disinterest, if someone would care for a proof, ask. It's
amateurish and I've forgotten half of it, I'll probably forget the other
half
by tomorrow.

 -Kaatunut

/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
#include <stdio.h>
#include <stdlib.h>

int main(int argc,char* argv[]) {
    char buff[400];
    int Dm,DM,nm,nM;
    int D,n;

    printf("D search range start? ");
    fgets(buff,400,stdin);
    Dm=strtol(buff,NULL,0);
    printf("D end (-1 for endless)? ");
    fgets(buff,400,stdin);
    DM=strtol(buff,NULL,0);

    printf("n start? ");
    fgets(buff,400,stdin);
    nm=strtol(buff,NULL,0);
    printf("n end (-1 for endless)? ");
    fgets(buff,400,stdin);
    nM=strtol(buff,NULL,0);

    for (D=Dm;DM==-1 || D<=DM;++D)
        for (n=nm;nM==-1 || n<nM;++n) {
            int q=1,p;
            for (p=1;p<=n && (q!=1 || p==1);++p)
                q=(D*q)%n;
            if (p==n)
                printf("(%d,%d)\n",D,n);
        }
}
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

It's (as you see) in C, but it won't be hard to rewrite this in any
(s4,icon,vb) programming language...
Hope it's worth reading...


Rgds,

--Rafal Sulejman <[e-mail]>


<----  End Forwarded Message  ---->

Gordon Peterson                  http://personal.terabites.com/
Support the Anti-SPAM Amendment!  Join at http://www.cauce.org/
12/19/98: Partisan Republicans scornfully ignore the voters they "represent".
12/09/00: the date the Republican Party took down democracy in America.